
/*------------------------------------------

A suffix tree implementation for PAT-Array

------------------------------------------*/
#ifndef __SUFFIX_TREE_H
#define __SUFFIX_TREE_H

#include <math.h>
#include "sentence.h"

struct SuffixTreeNode
{
	wchar_t state;
	int counter;
	
	int endWithNullCounter;
	int stringTailLength;
	
	int children_size;
	int children_capacity;
	SuffixTreeNode* nodeList;
	

	/*
	 * This list is used to remember all tail string of current node.
	 */
	WordBeginEnd* tailHead;
	
	/*
	 *	This list is used to remember all the sentences that contain
	 *  the same prefix from root to current node.
	 */
	WordBeginEnd *head;

	SuffixTreeNode()
	{
		state = 0;
		counter = 0;
		endWithNullCounter=0;

		children_capacity = 0;
		children_size = 0;

		nodeList = 0;
		stringTailLength= 0;

		head = new WordBeginEnd();
		tailHead = new WordBeginEnd();
	}

	~SuffixTreeNode()
	{	
	}
	
	void addSentenceSection(Sentence * se, wchar_t * begin, wchar_t *end)
	{
		WordBeginEnd * section = new WordBeginEnd(se,begin,end);
		section->next = head ->next;
		head->next = section;

	}
	SuffixTreeNode* addChildNode(wchar_t s)
	{
		if(children_size == children_capacity)
			realloc_node_list();
		nodeList[children_size].state = s;

		children_size++;
		
		return &nodeList[children_size-1];
	}

	void addStringTail(Sentence *s, wchar_t *begin, wchar_t *cur)
	{
		WordBeginEnd *node = new WordBeginEnd(s,begin,cur);
		node->next = tailHead->next;
		tailHead ->next = node;
		
		++stringTailLength;
	}
	void removeStringTail(WordBeginEnd * node)
	{
		WordBeginEnd *cur;
		for(cur=tailHead; cur!=0; cur = cur->next)
		{
			if(cur->next == node)
			{
				cur->next= cur->next->next;
				delete node;
				break;
			}
		}
		--stringTailLength;

		if(cur == 0 || stringTailLength<0)
		{
			printf("\ncur: %x stringTailLeng %d!!!!\n",cur,stringTailLength);
			getchar();
		}
	}

	double entropy()
	{
		double result=0.0;
		double totalTimes = this->counter;
		
		// children
		for(int i = 0; i <children_size; ++i)
		{
			int times = this->nodeList[i].counter;
			result += times*log(times/totalTimes);
		}
		//tail string
		int num = this->stringTailLength;
		if(num > 0)
		{
			result += num * 1 * log(1/totalTimes);
		}
		//some times this node is end of string.
		int times = this->endWithNullCounter;
		if(times > 0)
		{
			result += times*log(times/totalTimes);
		}

		return abs(result);
	}

	void free()
	{
		for(int i = 0; i < children_size; ++i)
			nodeList[i].free();
		if (nodeList != 0)
		{
			delete [] nodeList;
			nodeList = 0;
		}
				
		freeWordBeginEndList(head);
		freeWordBeginEndList(tailHead);
	}
	void freeWordBeginEndList(WordBeginEnd *head)
	{
		for(WordBeginEnd *cur = head->next; cur!=0;)
		{
			WordBeginEnd *next = cur->next;
			delete cur;
			cur = next;
		}
		delete head;
	}
private:
	void realloc_node_list()
	{
		if(children_capacity==0)
		{
			children_capacity = 2;
			nodeList = new SuffixTreeNode[children_capacity];
		}
		else
		{
			children_capacity *= 2;
			SuffixTreeNode * newNodeList = new SuffixTreeNode[children_capacity];
			for( int i = 0; i < children_size; ++i)
				newNodeList[i] = nodeList[i];
			delete [] nodeList;
			nodeList = newNodeList;
		}
	}
};


// used to collate context information
struct WordContext
{
	wchar_t *str;
	int length;

	SuffixTreeNode * treeNode;

	WordContext()
	{
		length = 0;
		str=0;
		treeNode=0;
	}

	~WordContext()
	{
		delete [] str;
	}
};

class SuffixTree
{
public:
	//define wheter it is usted to represent left pat-array or right pat-array.
	enum TREE_TYPE { LEFT_SUFFIX_TREE=0xBABE001, RIGHT_SUFFIX_TREE=0xBABE002 };

private:
	int minMumWordLength;
	SuffixTreeNode *root;
	TREE_TYPE type;	

public:

	SuffixTree(TREE_TYPE );
	~SuffixTree();
	
	// insert at root postion
	void insert(Sentence * sen, wchar_t * wstring);

	void collectWordContext(WordContext* & context,int& size);
	void travel();
	
private:
	// insert at a tree node
	void insert(SuffixTreeNode * cur, Sentence *s, wchar_t *begin, wchar_t* wstring);
	void appendAsChildOrStringTail(SuffixTreeNode * cur, Sentence *s, wchar_t *begin, wchar_t* wstring);
	void addSentenceSection(SuffixTreeNode *node,Sentence *s, wchar_t *begin, wchar_t *end);
//	bool prepareAppendAsChildOrStringTail(SuffixTreeNode *node,Sentence *s, wchar_t *begin, wchar_t *end);

	void travel(SuffixTreeNode *node,wchar_t *prefix, int depth);
	void appendToPrefix(wchar_t * prefix, wchar_t state, wchar_t *newResult, int length);
	/*
	 * node :		current tree root.
	 * curdepth:	current root's parent depth in tree.
	 * prefix:		the prefix string of current string(exclude the state stored in itself)
	 * list:		used to remember all data.
	 * index:		the index of list where to store the data.
	 */
	void collectWordContext(SuffixTreeNode *node, int curdepth, wchar_t* prefix, WordContext* list,int& index);
	
};	

// count how many node are there below and equal a depth.
int countNodes(SuffixTreeNode *root,int curdepth, int depth);
int countWordInserted(SuffixTreeNode *root);

#endif